package com.cet.algorithm.二叉树.二叉树的最近公共祖先;

/**
 * @program: cet-practice
 * @description: 二叉树的最近公共祖先
 * @author: 陈恩涛
 * @create: 2023-04-05 23:14
 **/
public class LC236 {

    public static void main(String[] args) {

    }

    /**
     *
     * @param root bt root node
     * @param p node p
     * @param q node q
     * @return nearest common root node
     */
    static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null || root.val == p.val || root.val == q.val) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left == null && right == null) {
            return null;
        } else if (left == null && right != null) {
            return right;
        } else if (left != null && right == null) {
            return left;
        } else {
            return root;
        }
    }
}
